Doit 的博客

Appearance

文档协同编辑能力 - OT 算法 ​

🗿 认识协同编辑 ​

🤔 什么是协同编辑 ​

协同编辑是指多个用户同时对同一个文档或项目进行编辑和修改的过程。在协同编辑中，多个用户可以在实时或异步的情况下共同编辑文档并观察其他用户的编辑内容。

👌 协同编辑好处

  • 实时协作
  • 提高生产力
  • 减少冲突和错误
  • 简化版本控制

那如何实现协同编辑呢❓ 这里主要用到了协作算法 OT 市场上有很多文档使用了 OT 算法 ，例如：

  • 讯飞文档
  • 石墨文档
  • 腾讯文档
  • Google Docs

🤖 认识 OT 算法 ​

🙋🏻‍♂️ 先来看看有哪些处理冲突的方式

  1. 加锁：某一文档或段落同时只运行一个用户编辑，例如用户 A 在编辑时，就锁住文档或段落，只能 A 进行更新。用户 B 就不能编辑，或编辑后提交修改被服务器丢弃； image
  2. 覆盖： 谁最后修改，就全量使用他的修改，更早一些的其他人的修改会被丢弃； image
  3. 用户自行处理冲突： 就像 git merge/rebase 导致的冲突一样，会提示哪个地方被同时修改了，让合并者手动选择使用哪一个修改；
  4. 使用一致性算法： 比如接下来要介绍的 OT 算法，多用户编辑进行算法处理调整，在多个客户端生成一致的修改结果。

什么是 OT 算法 ​

OT （ Operational Transformation ）, 是一种基于操作转换的协同冲突处理的收敛算法； 它的基本原理是通过对操作的转换和合并，确保多个用户同时编辑时的最终结果上的一致性。

操作 ​

这里的 操作 指的对文档的编辑，在 OT 里面对文档定义了三种操作：

  1. insert 插入操作
  2. retain 保留操作
  3. delete 删除操作

e.g. 插入 insert image e.g. 保留 retain image e.g. 删除 delete image

那 转换 和 合并 指的什么呢？ 继续往下 ⬇️

💭 首先看下协同编辑为什么需要 OT 算法 ​

举个 🌰 ，多人编辑在没有 OT 算法会出现什么情况 假设现在一个协作的文档初始内容是 hello ，甲乙都在同时编辑，甲端用户在 hello 后面插入了一个 a ，乙端用户在 hello 后面插入了一个 b ;

1️⃣ 对于甲客户端：

  1. 插入了 a 后，文档内容变成 helloa
  2. 然后接收到 乙端 的消息， 在 helloa 后面插入 b
  3. 最终文档内容变为 helloba

image

2️⃣ 对于乙客户端：

  1. 插入了 b 后，文档内容变成 hellob
  2. 然后接收到 甲端 的消息， 在 hellob 后面插入 a
  3. 最终文档内容变为 helloab

image

将上述内容的量化为模型图 ：

image

此时这时候 甲 乙 双端已经不一致了，即产生了冲突。

解决冲突 Transfrom ​

继续上述的 🌰 ：

甲乙 内容出现了不一致， 那谁应该才是正确的呢 ？ 对于 OT 算法强调是最终一致性， 所以 helloab 或 helloba 似乎看起来都是正确的。

但是从服务端视角来看, 先到的操作先应用原则：

假如 甲 操作先到达服务端， 乙 操作后到达服务端：

image

甲端 内容先变成 helloa，准备应用 O2 操作(乙) ，先与 O1 操作进行一个转换 O2' = Transfrom(O2, O1) = insert(6, 'b') , 因为在 O2 操作前， O1 在位置 5 已经插了一个字符， 所以 需要将位置 +1 ，再应用转换后的 O2'

image

乙端 内容先变成 hellob, 准备应用 O1 操作(甲)，先与 O2 操作进行一个转换 O1' = Transfrom(O1, O2) = insert(5, 'a') , 因为 甲操作在先，在第 5 位置插入 a 对乙操作其实不会有影响

image

如果 乙 操作先到达服务端， 甲 操作后到达服务端，情况就正好与上面相反

从上面的案例看出

  • Transfrom 是核心解决冲突的所在，对操作进行转换；同时也可看出 时序性对 OT 的算法的重要性， 这个确定了操作之间应该如何去转换。
  • Transfrom 操作既发生在服务端：将基于某个版本的并发操作对象转换成串行操作；也发生在客户端，本地的修改还没来得及提交，就收到了服务端推送。

同时上面的案例是一个并行插入冲突的实例，还有常见的并行删除操作冲突、插入和删除操作的冲突等；

并行删除操作： 同时在同一位置进行删除操作

image

插入和删除操作： 同时在同一位置进行新增和删除操作

image

数据合并 compose ​

合并操作

  • 合并操作序列
  • 合并操作到文档

举个 🌰 文档初始内容为 hello

  1. 甲用户先在 hello 后面(第 5 位置)插入了 world
  2. 在 helloworld 后面（第 10 位置）插入了 ！
  3. 删除了 world (从第 5 位置开始到第 10 位置)
  4. 在 hello 后面(第 5 位置)插入了 ot

如果将 4 步操作合并为 1 步操作：

  1. 在 hello 后面插入了 ot!image

需要 compose 的场景：

  1. 短时间内频繁的操作可以进行合并，以减少提交次数以及版本数
  2. 离线编辑是大量的操作可以进行合并
  3. 历史记录查看一段时间内的操作集合
  4. 应用到文档中

👓 可视化示例 （基于 OTjs 和 CodeMiror 编辑器实现）： ​

Visualization of OT with a central server (operational-transformation.github.io)

🤏 OT 算法在文档中的应用 - Delta ​

文档中的文字文档采用的是 Quill 富文本编辑器 如下图 Quill 简化的架构：

  • Quill Core ： Formats 、插件模块、主题等
  • Delta ：富文本数据层，负责描述数据
  • Parchment ：富文本控制器层，可以理解为抽象的 dom

image

Delta ​

Delta 主要负责文本操作和格式化。是基于 OT 算法实现。

image

数据结构 / 设计规范 ​

Delta 中数据插入类型分为 纯文本 与 embed 嵌入式内容。通过 attributes 区分不同的表现形式，应用场景例如我们常见的 标题、加粗、斜体、列表等。

  • 扁平化数据
  • 紧凑型

扁平化数据 ​

Delta 中数据都是扁平的，没有子节点。那他如何表达 文档 Dom 树结构的？ 关键在于 Quill 假定富文本不存在块元素的嵌套，即一行中不能同时存在标题和列表。遇到换行符则新建一行作为块级别 tag open ，直到遇到下一个换行符，作为 tag close 。

javascript
var content = [
  {
    insert: 'Hello',
  },
  {
    insert: 'World',
    attributes: { bold: true },
  },
  {
    insert: {
      image: 'https://quilljs.com/logo.png',
    },
    attributes: { width: '100' },
  },
]

如上述代码中 image 就是一个 embed 类型，这种嵌入类型的文本长度为 1 , 类似于一个文字长度。

紧凑型 ​

必须约定 Delta 中的数据格式标识形式，同一个富文本仅有一种数据表示形式，否则同一种数据可能存在不同表示，例如表示 Hello Word 的不紧凑形式：

javascript
var content = [
  { insert: 'Hel' },
  { insert: 'lo' },
  { insert: 'World', attributes: { bold: true } },
]

下面的方式更明确，易于理解和维护：

javascript
var content = [
  { insert: 'Hello' },
  { insert: 'World', attributes: { bold: true } },
]

部分核心算法实现 ​

🍗 Push

  • Insert 插入
  • Retain 保留
  • Delete 删除

主要是处理富文本操作的一些场景，核心主要是一下：

  • 连续的 insert 、 retain 、 delete 需要判断做合并操作，对于 insert 、retain 则是 attrs 相同且 insert 都为 string 即可合并，
javascript
// 例如
new Delta().insert('hello').insert('world')
// push后
new Delta().insert('helloworld')

image

javascript
// 例如
new Delta().insert('hello').insert('world').retain(3).insert('!')
// push后
new Delta().insert('helloworld').retain(3).insert('!')

image

  • delete 之后的 insert ，会做顺序调整， 规范是放到 insert 后面（因为由于在同一索引处的删除之前或之后插入并不重要，因此始终倾向于先插入）；
javascript
new Delta().insert('hello').retain(3).delete(2).insert('!')

image

  • 其他场景则直接 push ops 即可。 这主要是为了 ops 数据格式的一致性，为了之后的各种操作运算做逻辑统一化处理。

🍟 Compose 合并操作 compose 合并文档，中有几条原则，决定计算规则：

  • insert / delete / retain ，类型相同时选择性直接合并；
  • insert 优先于 delete ；
  • delete 、 retain 同时存在时，按先后顺序执行；
javascript
const a = new Delta().insert('hello')
const b = new Delta().retain(5).insert('o')
const c = new Delta().retain(6).insert('t')

a.compose(b).compose(c)

image

🍔 Transform 转化

根据已有的 Delta 操作转换给定的 Delta 。 示例如下：

javascript
const a = new Delta().insert('12').retain(1).insert('34')
const b = new Delta().insert('ab').retain(1).insert('cd')

a.transform(b, true) // new
// 结果
new Delta().retain(2).insert('ab').retain(3).insert('cd')

image

该方法也是解决冲突的核心方法， transform 方法内部通过 Delta 数据建立两个单链表通过比较两个对象的操作序列，并根据一定的规则进行变换，从而解决冲突并保持编辑操作的一致性。

下面的 ①②③④ 指的遍历次数

image

e.g. 文档处理中文输入中间态 composition

image

来自讯飞文档中一些经验说 讯飞文档对富文本编辑器其实做了大量的定制化开发和优化；

  • 中文输入法适配 image
  • 扩展组件： 例如附件预览、多meta信息的图片以及图片操作、@功能
  • 版本兼容
  • 系统适配
  • 大文档的性能优化： 数据懒加载
  • 移动端适配
  • 离线数据一致性问题 image
  • 等等 ...

富文本编辑器本身也是一个很复杂的模块，感兴趣的我们可以会后继续探讨 🔬。

📡 拓展: CRDT 算法以及 Yjs ​

CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）算法的核心思想是确保所有副本之间的数据一致性，而无需进行复杂的操作转换。

CRDT算法的关键思想是将数据结构设计成满足局部操作的可交换性和结合性。这意味着每个节点可以自主地对其本地副本进行修改，并通过将其修改操作与其他节点的操作合并，最终实现数据一致性。

Yjs 一款强大的基于 CRDT 算法实现的协同编辑 JavaScript 库

  • 数据操作要满足交换律、结合律和幂等性
  • 基于 YATA 算法的并发冲突解决机制

Released under the MIT License.

Copyright © 2024-present Doit